Two Dice
My friend Alex Ryba uses interesting math questions in the CUNY Math Challenge. For the 2016 challenge they had the following problem.
Problem. Eve owns two six-sided dice. They are not necessarily fair dice and not necessarily weighted in the same manner. Eve promises to give Alice and Bob each a fabulous prize if they each roll the same sum with her dice. Eve wishes to design her two dice to minimize the likelihood that she has to buy two fabulous prizes. Can she weight them so that the probability for Alice and Bob to get prizes is less than 1/10?
The best outcome for Eve would be if she can weight the dice so that the sum is uniform. In this case the probability that Alice and Bob get the prizes is 1/11. Unfortunately for Eve, such a distribution of weight for the dice is impossible. There are many ways to prove it.
I found a beautiful argument by Hagen von Eitzen on the stack exchange: Let ai (correspondingly bi) be the probabilities that die A (correspondingly B) shows i + 1. It would be very useful later that that i ranges over {0,1,2,3,4,5} for both dice. Let f(z) = ∑ aizi and g(z) = ∑ bizi. Then the desired result is that f(z)g(z) = ∑j=010 zj/11. The roots of the right side are the non-real roots of unity. Therefore both f and g have no real roots. So, they must both have even degree. This implies a5=b5=0 and the coefficient of z10 in their product is also 0, contradiction.
Alex himself has a straightforward argument. The probabilities of 2 and 12 have to be equal to 1/11, therefore, a0b0 = a5b5 = 1/11. Then the probability of a total 7 is at least a0b5 + a0b5. The geometric mean of a0b5 and a0b5 is 1/11 (from above), so their arithmetic mean is at least 1/11 and their sum is at least 2/11. Therefore, the uniform distribution for sums is impossible.
So 1/11 is impossible, but how close to it can you get?
Share:
Kknop:
Lower bound 14/144. Example (3,0,0,0,0,3) (1,1,1,1,1,1).
14 December 2018, 1:47 amOscar Cunningham:
Lower bound 3/32. Example (1,0,0,0,0,1)/2 (2,3,3,3,3,2)/16.
14 December 2018, 12:19 pmOscar Cunningham:
I asked reddit for help: https://www.reddit.com/r/math/comments/a6tv25/two_dice_puzzle/
16 December 2018, 5:59 pmJim Roche:
Great blog, Tanya! I wish I’d found it years ago.
The minimal probability is indeed 3/32, and — up to switching the labels of the 2 dice — the unique pair of dice that achieves the minimum is Oscar’s: {(1,0,0,0,0,1)/2, (2,3,3,3,3,2)/16}. A proof sketch is below.
Let the distribution (pmf) of the sum of the values on the 2 dice (translated from 1-6 to 0-5) be
(p[0], …, p[10]), and let (a[0], …, a[5]) and (b[0], …, b[5]) be the pmf’s for the 2 individual dice.
The 2 key lemmas we need were already (essentially) given in Tanya’s 13 December 2018 post:
(1) For any m >= 1, if x[i] >= 0 for 1 <= i <= m and \sum_{1 <= i <= m} x[i] = C, then
\sum_{1 <= i <= m} x[i]^{2} is uniquely minimized when x[i] = C/m for all i, and then
\sum_{1 <= i = a[0]*b[5] + a[5]*b[0] >= 2*sqrt(a[0]*b[5]*a[5]*b[0]) [by the AM-GM inequality], so
p[5] >= 2*sqrt( (a[0]*b[0])*(a[5]*b[5]) ) = 2*sqrt(p[0]*p[10]).
Now we relax the conditions of the original problem and seek the minimum of \sum_{0 <= i = 2*sqrt(p[0]*p[10]). We will show that the minimum for this relaxed problem is 3/32, uniquely achieved when
p = (2,3,3,3,3,4,3,3,3,3,2)/32.
Then we will argue that this unique p is achieved as a convolution of a and b only for the pair of pmf’s {a,b} that Oscar found.
To solve the relaxed optimization problem, define r[0] := sqrt(p[0]), r[10] := sqrt(p[10]), and define the slack variable u >= 0 as u := p[5] – 2*r[0]*r[10]. It will turn out to be more convenient to work instead with the “product” variable P := r[0]*r[1] and the “quadratic” variable Q := (r[0] + r[1])^{2}, together with u.
Then we can express (p[0]^{2} + p[10]^{2}) + p[5]^2 as a quadratic function of P, Q, and u with the linear inequality constraints 0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u= 1, Q + u <= 1. Furthermore, for any fixed value of
p[0] + p[10] + p[5], by Lemma 1 we (uniquely) minimize the sum of the squares of the 8 remaining p[i]'s by making those 8 p[i]'s all equal. After a little algebra, we obtain the following transformed minimization problem (whose global minimum might not be achievable for the original problem, but which will not lose any solutions to the original problem):
min { (Q^{2} – 4*P*Q + 2*P^{2}) + (2*P + u)^{2} + (1/8)*(1 – Q – u )^{2}) }
s.t. 0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u= 1, Q + u 0, b[0] = b[5] > 0, and
either (a[1] = a[4] = 0, b[1] > 0, b[4] > 0) or (b[1] = b[4] = 0, a[1] > 0, a[4] > 0).
We continue by considering p[2] and p[8], obtaining more and more constraints on the a[i]’s and b[i]’s until all 12 values are nailed down as claimed (up to possible swapping of the a[] and b[] distributions).
31 March 2019, 12:42 pmJim Roche:
Sorry, my previous post seems to be missing various lines. I’ll try again, breaking into 2 pieces:
Part 1:
The minimal probability is indeed 3/32, and — up to switching the labels of the 2 dice — the unique pair of dice that achieves the minimum is Oscar’s: {(1,0,0,0,0,1)/2, (2,3,3,3,3,2)/16}. A proof sketch is below.
Let the distribution (pmf) of the sum of the values on the 2 dice (translated from 1-6 to 0-5) be
(p[0], …, p[10]), and let (a[0], …, a[5]) and (b[0], …, b[5]) be the pmf’s for the 2 individual dice.
The 2 key lemmas we need were already (essentially) given in Tanya’s 13 December 2018 post:
(1) For any m >= 1, if x[i] >= 0 for 1 <= i <= m and \sum_{1 <= i <= m} x[i] = C, then
\sum_{1 <= i <= m} x[i]^{2} is uniquely minimized when x[i] = C/m for all i, and then
\sum_{1 <= i = a[0]*b[5] + a[5]*b[0] >= 2*sqrt(a[0]*b[5]*a[5]*b[0]) [by the AM-GM inequality], so
p[5] >= 2*sqrt( (a[0]*b[0])*(a[5]*b[5]) ) = 2*sqrt(p[0]*p[10]).
Now we relax the conditions of the original problem and seek the minimum of \sum_{0 <= i = 2*sqrt(p[0]*p[10]). We will show that the minimum for this relaxed problem is 3/32, uniquely achieved when
p = (2,3,3,3,3,4,3,3,3,3,2)/32.
Then we will argue that this unique p is achieved as a convolution of a and b only for the pair of pmf’s {a,b} that Oscar found.
To solve the relaxed optimization problem, define r[0] := sqrt(p[0]), r[10] := sqrt(p[10]), and define the slack variable u >= 0 as u := p[5] – 2*r[0]*r[10]. It will turn out to be more convenient to work instead with the “product” variable P := r[0]*r[1] and the “quadratic” variable Q := (r[0] + r[1])^{2}, together with u.
Then we can express (p[0]^{2} + p[10]^{2}) + p[5]^2 as a quadratic function of P, Q, and u with the linear inequality constraints 0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u= 1, Q + u <= 1. Furthermore, for any fixed value of
p[0] + p[10] + p[5], by Lemma 1 we (uniquely) minimize the sum of the squares of the 8 remaining p[i]'s by making those 8 p[i]'s all equal. After a little algebra, we obtain the following transformed minimization problem (whose global minimum might not be achievable for the original problem, but which will not lose any solutions to the original problem):
min { (Q^{2} – 4*P*Q + 2*P^{2}) + (2*P + u)^{2} + (1/8)*(1 – Q – u )^{2}) }
s.t. 0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u= 1, Q + u <= 1.
31 March 2019, 12:52 pmJim Roche:
Ugh, my previous 2 comments were mangled, probably because some mathematical symbols were misinterpreted. Here’s one more attempt.
The minimal probability is indeed 3/32, and — up to switching the labels of the 2 dice — the unique pair of dice that achieves the minimum is Oscar’s: {(1,0,0,0,0,1)/2, (2,3,3,3,3,2)/16}. A proof sketch is below.
Let the distribution (pmf) of the sum of the values on the 2 dice (translated from 1-6 to 0-5 on each die) be
(p[0], …, p[10]), and let (a[0], …, a[5]) and (b[0], …, b[5]) be the pmf’s for the 2 individual dice.
The 2 key lemmas we need were already (essentially) given in Tanya’s 13 December 2018 post:
(1) For any m >= 1, if x[i] >= 0 for 1 <= i <= m and sum_{1 <= i <= m} x[i] = C, then
sum_{1 <= i <= m} x[i]^{2} is uniquely minimized when x[i] = C/m for all i, and then
sum_{1 <= i = a[0]*b[5] + a[5]*b[0] >= 2*sqrt(a[0]*b[5]*a[5]*b[0]) [by the AM-GM inequality], so
p[5] >= 2*sqrt( (a[0]*b[0])*(a[5]*b[5]) ) = 2*sqrt(p[0]*p[10]).
Now we relax the conditions of the original problem and seek the minimum of
sum_{0 <= i = 2*sqrt(p[0]*p[10]). We will show that the minimum for this relaxed problem is 3/32, uniquely achieved when
p = (2,3,3,3,3,4,3,3,3,3,2)/32.
Then we will argue that this unique p is achieved as a convolution of a and b only for the pair of pmf’s {a,b} that Oscar found.
To solve the relaxed optimization problem, define r[0] := sqrt(p[0]), r[10] := sqrt(p[10]), and define the slack variable u >= 0 as u := p[5] – 2*r[0]*r[10]. It will turn out to be more convenient to work instead with the “product” variable P := r[0]*r[1] and the “quadratic” variable Q := (r[0] + r[1])^{2}, together with u.
Then we can express (p[0]^{2} + p[10]^{2}) + p[5]^2 as a quadratic function of P, Q, and u with the linear inequality constraints
0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u= 1, Q + u <= 1.
Furthermore, for any fixed value of
p[0] + p[10] + p[5], by Lemma 1 we (uniquely) minimize the sum of the squares of the 8 remaining p[i]'s by making those 8 p[i]'s all equal. After a little algebra, we obtain the following transformed minimization problem (whose global minimum might not be achievable for the original problem, but which will not lose any solutions to the original problem):
min { (Q^{2} – 4*P*Q + 2*P^{2}) + (2*P + u)^{2} + (1/8)*(1 – Q – u )^{2}) }
31 March 2019, 11:16 pms.t. 0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u <= 1, Q + u 0, b[0] = b[5] > 0, and
either (a[1] = a[4] = 0, b[1] > 0, b[4] > 0) or (b[1] = b[4] = 0, a[1] > 0, a[4] > 0).
We continue by considering p[2] and p[8], obtaining more and more constraints on the a[i]’s and b[i]’s until all 12 values are nailed down as claimed (up to possible swapping of the a[] and b[] distributions).
Jim Roche:
Here’s a fourth attempt to post an ungarbled solution to the dice problem.
Great blog, Tanya! I wish I’d found it years ago.
The minimal probability is indeed 3/32, and — up to switching the labels of the 2 dice —
the unique pair of dice that achieves the minimum is Oscar’s:
{(1,0,0,0,0,1)/2, (2,3,3,3,3,2)/16}.
A proof sketch is below.
Let the distribution (pmf) of the sum of the values on the 2 dice
(translated from 1-6 to 0-5 on each die) be (p[0], …, p[10]), and
let (a[0], …, a[5]) and (b[0], …, b[5]) be the pmf’s for
the 2 individual dice. The 2 key lemmas we need were already (essentially)
given in Tanya’s 13 December 2018 post:
(1) For any m >= 1, if x[i] >= 0 for 1 <= i <= m and sum_{1 <= i <= m} x[i] = C,
then
sum_{1 <= i <= m} x[i]^{2} is uniquely minimized when x[i] = C/m for all i, and
then
sum_{1 <= i = a[0]*b[5] + a[5]*b[0] >= 2*sqrt(a[0]*b[5]*a[5]*b[0]) [by the AM-GM inequality],
so
p[5] >= 2*sqrt( (a[0]*b[0])*(a[5]*b[5]) ) = 2*sqrt(p[0]*p[10]).
Now we relax the conditions of the original problem and seek the minimum of
sum_{0 <= i = 2*sqrt(p[0]*p[10]). We will show that the minimum
for this relaxed problem is 3/32, uniquely achieved when
p = (2,3,3,3,3,4,3,3,3,3,2)/32.
Then we will argue that this unique p is achieved as a convolution of a and b only
for the pair of pmf’s {a,b} that Oscar found.
To solve the relaxed optimization problem, define r[0] := sqrt(p[0]),
r[10] := sqrt(p[10]), and define the slack variable
u >= 0 as u := p[5] – 2*r[0]*r[10].
It will turn out to be more convenient to work instead with the “product” variable
P := r[0]*r[1] and the “quadratic” variable Q := (r[0] + r[1])^{2}, together with u.
Then we can express (p[0]^{2} + p[10]^{2}) + p[5]^2 as a quadratic function of
P, Q, and u with the linear inequality constraints
0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u= 1, Q + u <= 1.
Furthermore, for any fixed value of p[0] + p[10] + p[5], by Lemma 1 we (uniquely) minimize
the sum of the squares of the 8 remaining p[i]'s by making those 8 p[i]'s all equal.
After a little algebra, we obtain the following transformed minimization problem
(whose global minimum might not be achievable for the original problem, but which will
not lose any solutions to the original problem):
min { (Q^{2} – 4*P*Q + 2*P^{2}) + (2*P + u)^{2} + (1/8)*(1 – Q – u )^{2}) }
s.t. 0 <= Q <= 1, 0 <= P <= Q/4 <= 1/4, 0 <= u <= 1, Q + u 0, b[0] = b[5] > 0, and either
(a[1] = a[4] = 0, b[1] > 0, b[4] > 0) or (b[1] = b[4] = 0, a[1] > 0, a[4] > 0).
We continue by considering p[2] and p[8], obtaining more and more constraints on
6 April 2019, 9:36 amthe a[i]’s and b[i]’s until all 12 values are nailed down as claimed (up to possible
swapping of the a[] and b[] distributions).